package ahaArithmetic;

//解救小哈（广度优先算法）
public class Bfs {

    static int[][] map = new int[][]{{0,0,1,0},{0,0,0,0},{0,0,1,0},{0,1,0,0},{0,0,0,1}};
    static int[][] next = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    static int x,y,s=0;
    static int startX = 0;
    static int startY = 0;
    static int endX = 3;
    static int endY = 2;
    static node[] nodes = new node[20];
    static int head = 0,tail=1;

    public static void main(String[] args) {
        for(int i=0;i<nodes.length;i++){
            nodes[i] = new node();
        }
        map[startX][startY] = 1;
        nodes[head].x=startX;
        nodes[head].y=startY;
        nodes[head].s=1;
        bfs();
    }

    public static void bfs(){

        while (head<tail){
            //四个方向走一遍
            for(int i=0;i<=3;i++){
                x = x + next[i][0];
                y = y + next[i][1];
                //判断越界
                if( x>4 || x<0 || y>3 || y<0){
                    x = nodes[head].x;
                    y = nodes[head].y;
                    continue;
                }
                //判断障碍
                else if(map[x][y]>0){
                    x = nodes[head].x;
                    y = nodes[head].y;
                    continue;
                }
                nodes[tail].x=x;
                nodes[tail].y=y;
                nodes[tail].s=nodes[head].s+1;
                nodes[tail].f=head;
                map[x][y] = nodes[tail].s;
                tail++;
                //System.out.println(x+" "+y);
                x = x - next[i][0];
                y = y - next[i][1];
            }
            //判断是否到达
            if(map[endX][endY] != 0){
                System.out.println(map[endX][endY]);
                bfs_print(tail-1);
                break;
            }
            head++;
            x = nodes[head].x;
            y = nodes[head].y;
        }
    }

    public static void bfs_print(int k){
        if(k==0){
            System.out.println(nodes[k].x+" "+nodes[k].y);
            return;
        }
        bfs_print(nodes[k].f);
        System.out.println(nodes[k].x+" "+nodes[k].y);
    }
}

class node{
    int x;
    int y;
    int s;
    int f;
}
